# 参考: https://leetcode-cn.com/problems/find-duplicate-subtrees/
# 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
#
# 两棵树重复是指它们具有相同的结构以及相同的结点值。
#
# 示例 1：
#
#         1
#        / \
#       2   3
#      /   / \
#     4   2   4
#        /
#       4
# 下面是两个重复的子树：
#
#       2
#      /
#     4
# 和
#
#     4
# 因此，你需要以列表的形式返回上述重复子树的根结点。
#
from typing import Optional, List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    @staticmethod
    def dfs_serialize(_node: TreeNode, _collector=None):
        if _collector is None:
            _collector = {}
        if _node.left:
            l = Solution.dfs_serialize(_node.left, _collector)
        else:
            l = '#'
        if _node.right:
            r = Solution.dfs_serialize(_node.right, _collector)
        else:
            r = '#'

        res = '%d,%s,%s' % (_node.val, l, r)
        if res in _collector:
            _collector[res].add(_node)
        else:
            _collector[res] = {_node}
        return res

    @staticmethod
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        if root:
            collector = {}
            Solution.dfs_serialize(root, collector)
            return [_nodes.pop() for key, _nodes in collector.items() if len(_nodes) > 1]
        else:
            return None


left = TreeNode(val=2, left=TreeNode(val=4))
right = TreeNode(val=3, left=TreeNode(val=2, left=TreeNode(val=4)), right=TreeNode(val=4))
node = TreeNode(val=1, left=left, right=right)

for each in Solution.findDuplicateSubtrees(Solution, root=node):
    collector_ = {}
    print('value: %s, serialized: %s' % (each.val, Solution.dfs_serialize(each, collector_)))

